{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Arranging Coins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: arrangeCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排列硬币"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你总共有&nbsp;<code>n</code><em>&nbsp;</em>枚硬币，并计划将它们按阶梯状排列。对于一个由 <code>k</code> 行组成的阶梯，其第 <code>i</code><em> </em>行必须正好有 <code>i</code><em> </em>枚硬币。阶梯的最后一行 <strong>可能</strong> 是不完整的。</p>\n",
    "\n",
    "<p>给你一个数字&nbsp;<code>n</code><em> </em>，计算并返回可形成 <strong>完整阶梯行</strong> 的总行数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/09/arrangecoins1-grid.jpg\" style=\"width: 253px; height: 253px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>因为第三行不完整，所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/09/arrangecoins2-grid.jpg\" style=\"width: 333px; height: 333px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>因为第四行不完整，所以返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [arranging-coins](https://leetcode.cn/problems/arranging-coins/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [arranging-coins](https://leetcode.cn/problems/arranging-coins/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n == 0 or n == 1:\n",
    "            return n\n",
    "        if n == 2:\n",
    "            return 1\n",
    "\n",
    "        start, end = 0, n\n",
    "\n",
    "        while start <= end:\n",
    "            mid = (start + end) // 2\n",
    "            num = mid * (1 + mid)/2\n",
    "            if num == n:\n",
    "                return mid\n",
    "            else:\n",
    "                if num > n:\n",
    "                    end = mid - 1\n",
    "                else:\n",
    "                    start = mid + 1\n",
    "\n",
    "        return start - 1\n",
    "\n",
    "        # mid:2\n",
    "        # num:2 * (1+2)/2=3\n",
    "        # end:3-1=2\n",
    "        # mid:(1+2)/2=1\n",
    "\n",
    "        # 1, 3\n",
    "        # mid: 2\n",
    "        # num: 2*(1+2)/2=3, end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        num_sum=0\n",
    "        num_list=[]\n",
    "        for i in range(0,n+1):\n",
    "            num_sum+=i\n",
    "            if num_sum>n:\n",
    "                break\n",
    "            num_list.append(i)\n",
    "        return max(num_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        res, count = 0, 1\n",
    "        while True:\n",
    "            res += count\n",
    "            if res > n:\n",
    "                return count-1\n",
    "            count+=1 \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        l, r = 1,n\n",
    "        while l < r:\n",
    "            mid = (l + r + 1)//2\n",
    "            if mid*(mid+1) <= 2*n:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        line, i = 0, 1\n",
    "        while n >= 0:\n",
    "            n -= i\n",
    "            i += 1\n",
    "            line += 1\n",
    "        return line-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        res = []\n",
    "        count = 1\n",
    "        while n > 0:\n",
    "            res.append(count)        \n",
    "            n -= count\n",
    "            count += 1\n",
    "            if count > n:\n",
    "                break\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        i = 1\n",
    "        sum = 0\n",
    "        cnt = 0\n",
    "        while n-sum >= i:\n",
    "            sum += i\n",
    "            i += 1\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if mid * (mid + 1) <= 2 * n:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def arrangeCoins(self, n: int) -> int:\r\n",
    "        import math\r\n",
    "        return math.floor((math.sqrt(1+8*n)-1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        ans,t = 0,1\n",
    "        while n>0:\n",
    "            n -= t\n",
    "            ans += 1\n",
    "            t += 1\n",
    "        return ans if n==0 else ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        k=1\n",
    "        x=n\n",
    "        while k<=x:\n",
    "            x=x-k\n",
    "            k+=1\n",
    "        return k-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        coinnum = 1\n",
    "        while n >= coinnum:\n",
    "            n -= coinnum\n",
    "            coinnum += 1\n",
    "        return coinnum-1\n",
    "        #用循环减去，并使得硬币数量加一\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        row = 0\n",
    "        while n > 0:\n",
    "            row += 1\n",
    "            n -= row\n",
    "        if n != 0:\n",
    "            row -= 1\n",
    "\n",
    "        return row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        return int(math.sqrt(2*n+0.25)-0.5)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        k = 1\n",
    "        while n >= 0:\n",
    "            n -= k\n",
    "            k += 1\n",
    "        return k - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        i=1\n",
    "        while n>0:\n",
    "            n-=i\n",
    "            i+=1\n",
    "        if n==0:\n",
    "            return i-1\n",
    "        return i-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        i = 1\n",
    "        while True:\n",
    "            n -= i\n",
    "            if n < 0:\n",
    "                return i-1\n",
    "            else:\n",
    "                i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        '''\n",
    "        k = 1\n",
    "        while True:\n",
    "            if (k+k*(k-1)/2) == n:      # 求和，如果相等，就直接输出k\n",
    "                return k\n",
    "                break\n",
    "            if (k+k*(k-1)/2) > n and (k-1+(k-1)*(k-2)/2)<n:     # 在二者中间，就输出k-1\n",
    "                return (k-1)\n",
    "                break\n",
    "            k = k + 1\n",
    "            '''\n",
    "\n",
    "        return (int((-1+(1+8*n)**0.5)/2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if n - i*(i+1)/2 < 0:\n",
    "                return i - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        sum=0\n",
    "        for i in range(1,n+1):\n",
    "            sum+=i\n",
    "            if sum>n:\n",
    "                return i-1\n",
    "            elif sum == n:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        flag = True\n",
    "        i = 0\n",
    "        sum_i = 0\n",
    "        while flag:\n",
    "            if sum_i < n:\n",
    "                i += 1\n",
    "                sum_i += i\n",
    "            else:\n",
    "                flag = False\n",
    "        if sum_i > n :\n",
    "            return i - 1\n",
    "        else:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        a = 1\n",
    "        while n >a-1:\n",
    "            n-=a\n",
    "            a +=1\n",
    "        return a-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        def a(num):\n",
    "            return (num*num+num)/2\n",
    "        left = 0\n",
    "        right = n+1\n",
    "        while right-left > 1:\n",
    "            mid = (right+left)//2\n",
    "            k = a(mid)\n",
    "            if n < k:\n",
    "                right = mid\n",
    "            if n >= k:\n",
    "                left = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        # i * (i+1) <= 2 * n\n",
    "        l, r = 1, n\n",
    "        n *= 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            s = mid * (mid + 1)\n",
    "            if s == n:\n",
    "                return mid\n",
    "            elif s > n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        k = int(sqrt(2*n))\n",
    "        if k*(k+1) > 2 * n:\n",
    "            k-=1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        sum = 0\n",
    "        i = 1\n",
    "        while True:\n",
    "            sum+=1\n",
    "            n=n-i\n",
    "            i+=1\n",
    "            if n==0:\n",
    "                return sum\n",
    "                break\n",
    "            elif n<0:\n",
    "                return (sum-1)\n",
    "                break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        i = 0\n",
    "        while(n >= 0):\n",
    "            i += 1\n",
    "            n = n - i\n",
    "            \n",
    "        return i - 1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        def a(num):\n",
    "            return (num*num+num)/2\n",
    "        left = 0\n",
    "        right = n+1\n",
    "        while right-left > 1:\n",
    "            mid = (right+left)//2\n",
    "            k = a(mid)\n",
    "            if n < k:\n",
    "                right = mid\n",
    "            if n >= k:\n",
    "                left = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        i = 1 #i表示第i层\n",
    "        while n > 0:\n",
    "            n -= i\n",
    "            i += 1\n",
    "        return i - 1 if n == 0 else i - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        p=0\n",
    "        q=0\n",
    "        while p<=n:\n",
    "            q+=1\n",
    "            p+=q\n",
    "        return q-1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        cur = 1\n",
    "        sum_nums = 0\n",
    "        while sum_nums < n :\n",
    "            cur += 1\n",
    "            sum_nums += cur\n",
    "        return cur - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        for i in range(int(n**0.5),n//2+2):\n",
    "            if i*(i+1)/2==n:\n",
    "                return i\n",
    "            elif i*(i+1)/2>n:\n",
    "                return i-1\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        k = int(sqrt(2*n))\n",
    "        if k*(k+1) > 2 * n:\n",
    "            k-=1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        count = 1\n",
    "        total = 0\n",
    "        while total < n:\n",
    "            count += 1\n",
    "            total = (1 + count) * count / 2\n",
    "        return count if total == n else count - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        success = False\n",
    "        i = 1\n",
    "        while not success:\n",
    "            if n > (i - 1) * i / 2:\n",
    "                if n < i * (i + 1) / 2:\n",
    "                    return i - 1\n",
    "                elif n == i * (i + 1) / 2:\n",
    "                    return i\n",
    "                else:\n",
    "                    i += 1\n",
    "            elif n == (i - 1) * i / 2:\n",
    "                return i - 1\n",
    "            else:\n",
    "                0\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        left=1\n",
    "        right=n\n",
    "\n",
    "        while left<right:\n",
    "            mid=(right+left+1)//2\n",
    "            \n",
    "            if n>=mid*(mid+1)/2:\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid-1\n",
    "\n",
    "        return left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        sum = 0\n",
    "        i = 0\n",
    "        while sum <= n:\n",
    "            i = i +1\n",
    "            sum = sum + i\n",
    "            \n",
    "        return i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        l, r = 1, n\n",
    "        n *= 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            s = mid * (mid + 1)\n",
    "            if s == n:\n",
    "                return mid\n",
    "            elif s > n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        return int(((1+8*n)**0.5-1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        res = 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        for i in range(0, 2**31-1):\n",
    "            res = res + i\n",
    "            if res > n:\n",
    "                return i - 1\n",
    "            elif res == n:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 思路1：解方程(k+1)*k=2n\n",
    "    ## 思路2：根据公式进行二分查找\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        ## 思路1实现\n",
    "        # return int(sqrt(2*n+1/4)-1/2)\n",
    "        ## 思路2实现\n",
    "        left, right = 1, n\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            res = mid * (mid + 1)\n",
    "            if res == 2 * n: return mid\n",
    "            elif res < 2 * n:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBlue(self, m, n):\n",
    "        if int((m*(m-1))/2) <= n:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        l = -1\n",
    "        r = n + 1\n",
    "\n",
    "        while l + 1 != r:\n",
    "            m = int((l+r)/2)\n",
    "\n",
    "            if self.isBlue(m, n):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        \n",
    "        return l - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        # 返回最大完整行的硬币数\n",
    "\n",
    "        # 用数学的取整办法解决\n",
    "        return int(( pow(8*n+1,0.5) - 1 ) / 2)\n",
    "        # 可以通过二分查找计算 nnn 枚硬币可形成的完整阶梯行的总行数。\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        for i in range(1,n+1):\n",
    "            if n<(1+i)*i/2:\n",
    "                return i-1\n",
    "            elif n==(1+i)*i/2:  \n",
    "                return i \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        return int(sqrt(n*2+0.25)-0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        return int((-1+sqrt(1+8*n))/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        # i * (i+1) <= 2 * n\n",
    "        l, r = 1, n\n",
    "        n *= 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            s = mid * (mid + 1)\n",
    "            if s == n:\n",
    "                return mid\n",
    "            elif s > n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        return int(sqrt(2*n+1/4)-1/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        l, r = 1, n\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if mid * (mid + 1) <= 2 * n:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        k=int((-1+(1+8*n)**0.5)/2)\n",
    "        return k+1 if n==k*(k-1)//2 else k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        index = 0\n",
    "        left = n\n",
    "        for i in range(1, n):\n",
    "            if left - i >= 0:\n",
    "                left -= i\n",
    "                index += 1\n",
    "            else:\n",
    "                break\n",
    "        return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(1,n+1):\n",
    "            if n>=i:\n",
    "                n = n-i\n",
    "                count+=1\n",
    "            else:\n",
    "                break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        t=0\n",
    "        i=0\n",
    "        while t<=n:\n",
    "            i+=1\n",
    "            t+=i\n",
    "        if t==n:\n",
    "            return i\n",
    "        else:\n",
    "            return i-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        ans = 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            sum = mid * (mid+1) // 2\n",
    "            if sum <= n:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def arrangeCoins(self, n: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(1, n+1):\r\n",
    "            ans += 1\r\n",
    "            n -= i\r\n",
    "            if n <= 0:\r\n",
    "                return ans if n==0 else ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        return math.floor((-1+math.sqrt(1+8*n))/2)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        result = 1\n",
    "        while True:\n",
    "            if n < result:\n",
    "                break\n",
    "            n = n - result\n",
    "            result += 1\n",
    "        return result - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        return int((pow(8 * n + 1, 0.5) - 1) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        b=1\n",
    "        while n>=b:\n",
    "            n-=b\n",
    "            b+=1\n",
    "        return b-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        a = 0\n",
    "        b = -1\n",
    "        while n >= 0:\n",
    "            a += 1\n",
    "            b += 1\n",
    "            n = n - a\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        left=0\n",
    "        right=(n+1)//2+1\n",
    "        while left<right-1:\n",
    "            mid=(left+right)//2\n",
    "            if mid*(mid+1)/2<=n:\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        i = 1\n",
    "        sum = 0\n",
    "        cnt = 0\n",
    "        while n-sum >= i:\n",
    "            sum += i\n",
    "            i += 1\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        # i * (i+1) <= 2 * n\n",
    "        l, r = 1, n\n",
    "        n *= 2\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            s = mid * (mid + 1)\n",
    "            if s == n:\n",
    "                return mid\n",
    "            elif s > n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        # n(n+1)/2\n",
    "        # 二分查找\n",
    "        l, r = 1, n\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if m * (m + 1) <= 2 * n:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# s = k*(1+k) / 2\n",
    "# we have s find min k\n",
    "# use bin to search min k\n",
    "# \n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            s = mid*(mid+1)>>1\n",
    "            if s == n:\n",
    "                return mid\n",
    "            if s>n:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        for index in range(1, n):\n",
    "            if ((1 + index - 1) * (index - 1) // 2 < n) and ((1 + index) * (index) // 2 > n):\n",
    "                return index - 1\n",
    "            elif ((1 + index - 1) * (index - 1) // 2 < n) and ((1 + index) * (index) // 2 == n):\n",
    "                return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def arrangeCoins(self, n: int) -> int:\r\n",
    "        return int((2*n+1/4)**(1/2) - 1/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        l, r = 1, n \n",
    "        res = 0\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            coins = (m / 2) * (1 + m)\n",
    "            if coins > n:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                res = m \n",
    "                l = m + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        有 n 個硬幣, 要排成樓梯形狀\n",
    "        樓梯有 k 列, i-th 列會有 i 個硬幣\n",
    "        最後一列的硬幣可能會不完全, 回傳 \"有幾個完成的幾列\"\n",
    "        \"\"\"\n",
    "        \n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        i = 1\n",
    "        while n > 0:\n",
    "            n -= i\n",
    "            if n == 0:\n",
    "                return i\n",
    "            i += 1\n",
    "        return i - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        i=0\n",
    "        while n>0:\n",
    "            i+=1\n",
    "            n-=i\n",
    "            \n",
    "\n",
    "        if n==0:\n",
    "            return i\n",
    "        else:\n",
    "            return i-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if i*(i+1)/2 > n:\n",
    "                return i-1\n",
    "            elif i*(i+1)/2 == n:\n",
    "                return i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        i = 1\n",
    "        ans = 0\n",
    "        while n >= i:\n",
    "            ans += 1\n",
    "            n -= i\n",
    "            #print(ans,n)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        i, j = 0, n\n",
    "        while i <= j:\n",
    "            mid = (i+j) >> 1\n",
    "            val = mid*(mid+1)//2\n",
    "            if val == n: return  mid\n",
    "            elif val > n: j = mid - 1\n",
    "            else: i = mid + 1\n",
    "        return i -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        l = 0\n",
    "        r = n + 1\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            check = (1+mid)*mid // 2\n",
    "            if check > n:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def arrangeCoins(self, n: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(1, n+1):\r\n",
    "            ans += 1\r\n",
    "            n -= i\r\n",
    "            if n <= 0:\r\n",
    "                return ans if n==0 else ans-1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
